package leetcode.p1728;

/**
 * @author: trtan
 * @create: 2021-02-23 12:39
 * @description: 猫捉老鼠 错误写法，写了好久，舍不得删
 **/
public class CatAndMouseII {
    public static void main(String[] args) {
        String[] grid = new String[]{"........","F...#C.M","........"};
        System.out.println(new CatAndMouseII().canMouseWin(grid, 1, 2));
    }
    /**
     * @author trtan
     * @date 2021/2/23 12:39
     * description:
     * @param grid 矩阵：C代表猫、M代表老鼠、#代表墙、.代表地板、F代表食物。
     * @param catJump 猫一次能往一个方向跳得最大距离(可以不动)
     * @param mouseJump 老鼠能一次往一个方向跳得最大距离(可以不动)
     * @return boolean
     */
    public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
        char[][] rebuildGrid = new char[grid.length][grid[0].length()];
        for (int i = 0; i < grid.length; i++) {
            rebuildGrid[i] = grid[i].toCharArray();
        }
        //定义一个数组，记录猫到所有点的最少移动次数
        int[][] cost = new int[rebuildGrid.length][rebuildGrid[0].length];
        boolean[][] vis = new boolean[rebuildGrid.length][rebuildGrid[0].length];
        //首先初始化，未计算时到每个点移动次数为无穷大，这里设为2000即可，因为老鼠最多走1000次
        //顺便记录猫、老鼠、食物的初始位置
        Point C = null, M = null, F = null;
        for (int i = 0; i < rebuildGrid.length; i++) {
            for (int j = 0; j < rebuildGrid[i].length; j++) {
                cost[i][j] = 2000;
                if (rebuildGrid[i][j] == 'C') C = new Point(i, j);
                else if (rebuildGrid[i][j] == 'M') M = new Point(i, j);
                else if (rebuildGrid[i][j] == 'F') F = new Point(i, j);
                vis[i][j] = false;
            }
        }
        //更新猫能到所有位置的最少时间
        cost[C.x][C.y] = 0;
        computationalCost(rebuildGrid, cost, C, catJump);
        for (int i = 0; i < rebuildGrid.length; i++) {
            for (int j = 0; j < rebuildGrid[i].length; j++) {
                System.out.print(rebuildGrid[i][j]);
            }
            System.out.println();
        }
        for (int i = 0; i < cost.length; i++) {
            for (int j = 0; j < cost[i].length; j++) {
                System.out.print(cost[i][j] + ", ");
            }
            System.out.println();
        }
        //判断老鼠是否能在1000次内吃到食物
        return dfs(rebuildGrid, vis, M) && mouseJumpFood(rebuildGrid, cost, M, 0, mouseJump);
    }

    boolean dfs(char[][] grid, boolean[][] vis, Point M) {
        if (grid[M.x][M.y] == 'F') return true;
        vis[M.x][M.y] = true;
        boolean flag = false;
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (i * j == 0 && i != j) {
                    int nx = M.x + i;
                    int ny = M.y + j;
                    //越界
                    if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length) continue;
                    //碰到墙
                    if (grid[nx][ny] == '#' || vis[nx][ny]) continue;
                    flag |= dfs(grid, vis, new Point(nx, ny));
                }
            }
        }
        return flag;
    }

    /**
     * @author trtan
     * @date 2021/2/23 13:09
     * description:
     * @param grid
     * @param cost
     * @param M 老鼠当前位置
     * @param count 当前已经走的次数
     * @param mouseJump 老鼠一次能走的最大距离
     * @return boolean
     */
    private boolean mouseJumpFood(char[][] grid, int[][] cost, Point M, int count, int mouseJump) {
        if (count > 1000) return false;
        //如果老鼠走在这个位置之前猫已经到了(也就是猫可以一直在这等老鼠来)
        if (count > cost[M.x][M.y]) return false;
        //如果当前老鼠已经在食物的位置了，就成功了 (注意这个条件放前边，存在猫和老鼠同意的步数到达F点，但此刻猫和老鼠虽然在同一个点，但老鼠先走，此时已经赢了)
        if (grid[M.x][M.y] == 'F') {
            System.out.println("-------" + M.x + ", " + M.y + "----------");
            return true;
        }
        if (count == cost[M.x][M.y]) return false;
        System.out.println("-------" + M.x + ", " + M.y + "----------");
        //成功失败标识
        boolean flag = false;
        //如果没有，继续往四个方向走
        for (int i = -mouseJump; i <= mouseJump; i++) {
            for (int j = -mouseJump; j <= mouseJump; j++) {
                if (i * j == 0) {
                    int nx = M.x + i;
                    int ny = M.y + j;
                    //越界
                    if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length) continue;
                    //碰到墙
                    if (grid[nx][ny] == '#') continue;
                    //在此需要判断该行该列是否有墙阻挡
                    if (checkWall(grid, M.x, M.y, nx, ny)) continue;
                    //如果任意情况有一次吃到食物就算成功
                    System.out.println(M.x + ", "  + M.y + ", " + nx +  ", " + ny);
                    flag |= mouseJumpFood(grid, cost, new Point(nx, ny), count + 1, mouseJump);
                    if (flag == true) break;
                }
            }
            if (flag == true) break;
        }
        return flag;
    }
    /**
     * @author trtan
     * @date 2021/2/23 12:56
     * description: 计算猫到各个点的最少移动次数
     * @param grid
     * @param cost
     * @param C 猫当前的位置
     * @param catJump 猫一次能走的最大距离
     */
    private void computationalCost(char[][] grid, int[][] cost, Point C, int catJump) {
        //上下左右四个方向
        for (int i = -catJump; i <= catJump; i++) {
            for (int j = -catJump; j <= catJump; j++) {
                if (i * j == 0) {
                    int nx = C.x + i;
                    int ny = C.y + j;
                    //越界
                    if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length) continue;
                    //碰到墙
                    if (grid[nx][ny] == '#') continue;
                    //在此需要判断该行该列是否有墙阻挡
                    if (checkWall(grid, C.x, C.y, nx, ny)) continue;
                    //如果到达点的最少次数可以更新，那么就可以继续更新到达与"到达点到达的点"的最少次数，直到无点可更新
//                    System.out.println(C.x + ", "  + C.y + ", " + nx +  ", " + ny);
                    if (cost[nx][ny] > cost[C.x][C.y] + 1) {
                        cost[nx][ny] = cost[C.x][C.y] + 1;
                        computationalCost(grid, cost, new Point(nx, ny), catJump);
                    }
                }
            }
        }
    }

    /**
     * @author trtan
     * @date 2021/2/23 13:38
     * description: 如果两点间有墙return true
     * @param grid
     * @param x
     * @param y
     * @param nx
     * @param ny
     * @return boolean
     */
    private boolean checkWall(char[][] grid, int x, int y, int nx, int ny) {
        int l = Math.min(x, nx);
        int r = Math.max(x, nx);
        for (int i = l; i <= r; i++) {
            if (grid[i][y] == '#') return true;
        }
        l = Math.min(y, ny);
        r = Math.max(y, ny);
        for (int i = l; i <= r; i++) {
            if (grid[x][i] == '#') return true;
        }
        return false;
    }

    private static class Point {
        Integer x, y;
        Point() {}
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}
